//快速排序
function sort(array) {

    if (array.length < 2) {
        return array
    }

    let xIndex = Math.floor(Math.random * array.length)
    let x = array.splice(xIndex, 1)[0]

    let left = []
    let right = []

    for (let i = 0; i < array.length; i++) {
        if (array[i] < x) {
            left.push(array[i])
        } else if (array[i] > x) {
            right.push(array[i])
        }
    }

    return [...sort(left), x, ...sort(right)]

}

let array = [5, 4, 9, 2, 8, 3, 7, 6, 1]

console.log(sort(array));
